Minimum size subarray Sum [Binary Search]

Time: O(N); Space: O(1); medium

Given an array of N positive integers and a positive integer S, find the minimal length of a contiguous subarray of which the sum >= S. If there isn’t one, return 0 instead.

Example 1:

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation:

  • The subarray [4,3] has the minimal length under the problem constraint.

Follow up:

  • If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

[10]:

class Solution1(object):
    """
    Time:  O(n)
    Space: O(1)
    """
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        sums = {}
        cur_sum, min_len, max_len = 0, float("inf"), 0

        for i in range(len(nums)):
            cur_sum += nums[i]
            if cur_sum == s:
                min_len = i + 1
            elif cur_sum - s in sums:
                min_len = min(min_len, i - sums[cur_sum - s])
            if cur_sum not in sums:
                sums[cur_sum] = i  # Only keep the smallest index

        return min_len

[12]:

sol = Solution1()
s = 7
nums = [2,3,1,2,4,3]
assert sol.minSubArrayLen(s, nums) == 2

Binary search solution

[18]:


class Solution2(object):
    """
    Binary search solution
    Time:  O(NLogN)
    Space: O(N)
    """
    def binarySearch(self, compare, A, start, end, target):
        while start < end:
            mid = start + (end - start) // 2
            if compare(target, A[mid]):
                end = mid
            else:
                start = mid + 1
        return start

    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        min_size = float("inf")
        sum_from_start = [n for n in nums]

        for i in range(len(sum_from_start) - 1):
            sum_from_start[i + 1] += sum_from_start[i]

        for i in range(len(sum_from_start)):
            end = self.binarySearch(lambda x, y: x <= y, sum_from_start, \
                                    i, len(sum_from_start), \
                                    sum_from_start[i] - nums[i] + s)
            if end < len(sum_from_start):
                min_size = min(min_size, end - i + 1)

        return min_size if min_size != float("inf") else 0



[19]:

sol = Solution2()
s = 7
nums = [2,3,1,2,4,3]
assert sol.minSubArrayLen(s, nums) == 2